package demo22;

import java.util.ArrayList;
import java.util.List;

/*
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */

public class Test {
    public static void main(String[] args) {
        List<String> result = generateParenthesis(3);
        for (String s : result) {
            System.out.println(s);
        }
    }


    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList();
        findResult(result,0,n,"");
        return result;
    }

    /*
        result：用来保存最终结果集的集合
        stack：用来模拟栈，每进入一个左括号，就+1，出栈就-1
        num：当前还要匹配多少完整的括号才结束
        str：当前所拼接出的字符串
     */
    public static void findResult(List<String> result, int stack, int num, String str){
        if(num == 1){
            //剩下最后一组要匹配的字符串
            if(stack == 1){
                //栈内有一个左括号，所以只需要加一个右括号即可
                result.add(str+")");
            }else if(stack == 0){
                //栈内没有左括号，所以需要加完整的左右括号
                result.add(str+"()");
            }
            //递归终点
            return;
        }
        //将大问题拆解成小问题
        if(stack >= num){
            //栈还可以放左括号，这里分两种情况探讨
            if(stack != 0){
                //1.选择与栈内的括号匹配
                findResult(result,stack-1,num-1,str+")");
            }
            //2.选择继续压栈，放一个左括号进栈
            findResult(result,stack+1,num,str+"(");
        }else{
            //栈已经不能放左括号了，只能用右括号与栈内匹配了
            findResult(result,stack-1,num-1,str+")");
        }
    }
}
